package interview.arrayintersection;

import java.util.ArrayList;
import java.util.Arrays;

public class ArrayIntersection {
	public ArrayList<Integer> intersection(int[] A, int[] B) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		int Aidx = 0, Bidx = 0;
		int Alen = A.length, Blen = B.length;
		int idx = -1;
		while(Aidx < Alen && Bidx < Blen) {
			if(A[Aidx] < B[Bidx]) {
				idx = Arrays.binarySearch(A, B[Bidx]);
				if(idx < 0) {
					idx = (idx + 1) * (-1);
					Aidx = idx;
				} else {
					result.add(A[idx]);
					Aidx = idx + 1;
				}
			} else {
				idx = Arrays.binarySearch(B, A[Aidx]);
				if(idx < 0) {
					idx = (idx + 1) * (-1);
					Bidx = idx;
				} else {
					result.add(B[idx]);
					Bidx = idx + 1;
				}
			}
		}
		return result;
	}
}
